1. Field of the Invention
The method and apparatus of the present invention relates to dithering techniques used to represent digital images. More particularly, the method and apparatus of the present invention relates to exploiting the full dynamic range of intensities and distributing the quantization error over the entire intensity range.
2. Related Applications
The present invention is related to U.S. applications Ser. No. 07/909,125, filed Jul. 6, 1992, entitled "Method and Apparatus For Vector Aligned Dithering", U.S. application Ser. No. 07/413,991, filed Sep. 28, 1989, entitled "Method and Apparatus for Non-Linear Dithering of Digital Images", and U.S. Pat. No. 5,164,717, entitled "Method and Apparatus for the Dithering of Anti-Aliased Vectors", and are herein incorporated by reference.
3. Art Background
A picture or image may be thought of as a continuous representation of the object projected. It is often desirable to represent images on a digital computer display device such as a monitor or a printer. However, a computer and its output devices are binary in nature. A computer display comprises a grid of display elements, referred to as pixels, which can either be in one of a plurality of on states indicative of its intensity, in which the pixel location is illuminated, or in the off state in which the pixel location is not illuminated. In order to display continuous images, the continuous images must be converted to discrete representations corresponding to the pixel locations on the display device. A digital image is quantized in both the spatial domain and the intensity domain.
The amount of memory available dictates the quantized levels available to represent the image. If the resolution of either sample space (i.e. spatial and intensity) drops below a threshold (due to memory limitations), the eye will detect the discrete boundaries between samples. In the intensity domain, insuffient resolution is marked by the presence of artificial edges delimiting the transitions between regions of incremental intensity. Other undesirable visible effects, such as patterning, color shifting and biasing, are introduced due to the visible thresholding between quantized intensity levels.
To minimize the undesirable effects, a technique, referred to as dithering or digital halftoning, is used. Dithering is a technique which permits the simulation of intensity levels between quantized levels by permitting the eye to integrate fine detail within an area and record only the overall intensity of the area. Dithering aims to sacrifice some of an image's spatial resolution for an increase in perceived intensity resolution, accomplished by averaging the intensities of several neighboring pixels to simulate intensities that lie between quantization levels. Typically, this technique works well, since the eye naturally blends individual pixel values such that only the average intensity in the surrounding area or neighborhood is perceived. For more information on dithering, see Ulichney, Digital Halftoning (1987, MIT Press); Foley & Van Dam, Fundamentals of Interactive Computer Graphics, p. 597-602 (Addison-, Wesley, 1984).
Several types of dithering techniques exist. The types of dithering algorithms are distinguished by the way the neighborhoods are chosen. In the technique of ordered dither, the neighborhoods are chosen according to a two dimensional set of values, referred to as the dither table or dither matrix, which is tiled into the image's coordinate space. Typically for area dither, the table has the same number of row and column elements and the total number of entries in the table equals the number of simulatable intensity levels between the quantized levels. The values contained in the table are used to make decisions about which quantized intensity value will be output at each position, that is, should the intensity value be quantized to the quantized value above or below the original intensity value. The dither table values are different at each x,y coordinate location such that when a constant input intensity is dithered over some area, the output values will alternate in some pattern between the upper and lower quantized intensity levels.
The ordered dither process is explained in reference to FIG. 1. Process 1.0 determines the appropriate index into the dither matrix based on the x-y coordinates of the current pixel. Conceptually, the idea is to "tile" the dither matrix into the image coordinate space, thereby replicating each entry once every n pixels, where n is the dimension of the dither table. The indices to the matrix, i-j, are determined according to the following equations: EQU i=x mod n EQU j=y mod n
If n is a power of two, then it is possible to utilize the least significant bits of the x-y screen coordinates for indexing the dither matrix. For example, if the dimension of the dither matrix is 4.times.4, then the 2 least significant bits of the x-y coordinates will provide the required modulo-4 indexing.
At process 2.0, the dither values are retrieved from the matrix according to i-j dither indices determined. By the nature of the problem, the output intensity scale has fewer entries than the input intensity scale. In order to quantize the input value, there must be a predetermined correspondence between each level on the output scale to a value on the input scale. It is the task of process 3.0 to determine the input-scale base value, which is the input scale value that is nearest to but not greater than the original input intensity and which directly corresponds to a value in the stored range of intensities (output intensity values). The next process, 4.0, determines the value in the stored range of quantized intensity levels that corresponds to the input-scale base value. This value will be referred to as the "stored range base value".
At process 5.0, the difference between the input intensity value and the intensity of its input-scale base value is determined. The result, always guaranteed to be greater than or equal to zero, is the delta value passed along to process 6.0. Process 6.0 is the pivotal dither process, comparing the delta value to the dither value and outputting either the stored range base value or the next higher value. Specifically, if the delta value is less than or equal to the dither value, the stored range base value is output; if delta is greater than the dither value, then the stored range base plus one is output. The output from process 6.0 is the quantized pixel value that is deposited into the pixel store (e.g. a frame buffer).
Although quantized values are stored, these values are typically mapped back to an intensity scale with a greater intensity range for display viewing. That is the task of process 7.0, which is usually implemented by lookup-tables lying between the frame buffer output and the video display input. (This is not part of dithering per se, but is utilized for reconstruction of the dithered image for viewing.)
By performing processes 1.0 through 6.0 on successive input values, dithering causes values both greater than and less than the input intensity to ultimately be displayed, producing regions over which the overall average intensity is approximately equal to the original input intensity.
The dithering process is applied to all portions of the digital image for all intensities. Linearly mapping the output intensity scale, typically via look-up tables, to a range such as 0-255, implies that the dithered pixel values are quantized with even distribution of error throughout the entire range of inputs. However, an error distribution problem arises during the dithering process. The error is not evenly distributed or balanced such that the high end of the intensity scale is not mapped to the highest portions of the output intensity scale. That is, the high intensity values are clipped resulting in the loss of image brightness.
The problem may best be understood by first examining the error distribution with regards to simplified situation of quantization without dithering (note that the illustration and examples are set forth in hexadecimal numbers).
Consider an 8 bit input value hl, where h=the number corresponding to the most significant 4 bits, and l=the number corresponding to the least significant 4 bits. The most expedient way to compress hl into 4 bits is to truncate its least significant half. Specifically, if q(hl) is the 4 bit result after quantization, then ##EQU1##
The value q(hl), which is stored in the 4 bit frame buffer, must undergo some output mapping (typically via a lookup table) for display. Since q(hl) was created by a right shift of 4 bits, a logical output mapping may be one which performs a complementary 4 bit shift to the left. The output function, out (), will have sixteen entries: EQU out(i)=i0, where i.epsilon.[0, 0f]
Therefore, for some quantized value q(hl), the observed output will be EQU out[q(hl)]=out(0h)=h0
Over some spatial domain composed entirely of input value hl, the average output value is EQU average (hl)=h0
and, for regions of intensity hl, the average error per pixel is ##EQU2##
Given an input scale of 0-ff, FIG. 2a illustrates the output resulting from quantization by truncation, and FIG. 2b the average error incurred. A problem that is immediately clear from FIG. 2a is that, although the low end of the intensity scale maps properly (from 0 to 0), the high end clipped to a maximum of fifteen graduations short of the original maximum intensity. From FIG. 2b it can be seen that the error function swings between 0 and f, which is excessive particularly at intensities approaching zero. From an observer's point of view, this will translate into the artificial contours in the output image. In addition, the quantization error is distributed throughout the intensity scale, but is all of the same sign. As a result, overall image energy is not conserved and the brightness of the 4 bit image is noticeably attenuated.
Typically, prior art methods for 8 bit to 4 bit dithering rely upon the same basic principle as the direct quantization method described above, that of shifting out the least significant four bits. The twist is that, before the bit-shift, an entry from the dither table is added to the incoming pixel value and the result is clipped to ff.
The strategy will only work if the dither table contains entries in the range 0-0f, as this range of values will cause a maximum increment of 1 in the high 4 bits of the input which the addition is performed. Correspondingly, when the result is shifted 4 bits to the right, the quantized value for some input hl (as defined earlier) will be either h or h+1, depending on the dither value.
Analytically, the equation of the quantized value q(hl) is EQU q(hl)=[min[ff,(hl+0d)]&gt;&gt;4]& 0f
where the value d is an entry from the dither table. The equation of the quantized value (hl) may also be described algorithmically: ##EQU3##
As was the case in the earlier description, the 4 bit value q(hl) must be mapped to the full range of displayable intensities for viewing. Using the same sixteen-entry output function, out (), EQU out(i)=i0, where i.epsilon.[0, 0f]
the displayed outputs will then be ##STR1##
The average output has more relevance now than it did in the straight quantization illustration. Since the purpose of dithering is to create an ensemble average over the area of the dither table which is equal to the input value, then evaluating the average will enable us to calculate the net error from dithering. Based on the three possible cases for out (q(hl)), the average is determined according to the following: ##STR2##
The error, averaged over all pixels in the dither table's neighborhood, is therefore ##EQU4##
FIGS. 3a and 3b respectively illustrate the average output and error functions. Although the results show zero error for all inputs between 0 and f0, the fifteen highest intensities, f1-ff, are lost, just as the fifteen highest intensities were lost in the straight quantization illustration. Thus, for all images which contain a significant number of pixels in the high intensity range there will be a perceived loss of brightness due to the clipped high intensity values. In addition image energy is not conserved because the error is neither evenly distributed nor balanced.
Another problem which frequently occurs is the error introduced when the size of the interval (i.e., the number of values between prequantized intensity values) is not equal to the number of values in the dither matrix. The dither matrix values are arranged with the assumption that the number of values in the interval equals the number of values in the matrix. When not equal, the correct proportion of base and base +1 intensity values does not occur and the accuracy required to simulate the intermediate intensity values is diminished. For example, if the dither matrix contains 16 values (0-15) and the size of the interval was 4 (0-3), the distance value can never be greater than 4. Thus, dither matrix values 5 through 15 would always result in the base +1 intensity value being output resulting in a larger number of base +1 intensity values than the proportional amount needed to best simulate the intermediate intensity levels.